/*
    XTU OJ: 1340
    by: fifth_light
*/

#include <stdio.h>
#include <stdint.h>
#include <inttypes.h>

int64_t table[42] = {1, 3, 7, 19, 51, 141, 393, 1107, 3139, 8953, 25653, 73789, 212941, 616227, 1787607, 5196627, 15134931, 44152809, 128996853, 377379369, 1105350729, 3241135527, 9513228123, 27948336381, 82176836301, 241813226151, 712070156203, 2098240353907, 6186675630819, 18252025766941, 53876592856681, 159114492071763, 470139239360787, 1389754816243449, 4109922421017093, 12159131877715993, 35986168879543609, 106542797484006471, 315544068167601787, 934837217271732457, 2770417140954208377, 8212609533895771131};

int main(void) {
    int t;
    scanf("%d", &t);
    for(int i = 0; i < t; i++) {
        int num;
        scanf("%d", &num);
        printf("%" PRId64 "\n", table[num - 1]);
    }
    return 0;
}
